#include <iostream>
#include <vector> 
#define MAXSIZE_V 10//资源种类的最大值
#define MAXSIZE_P 20//进程数目的最大值
using namespace std;

//定义数据结构,全局变量
int Available[MAXSIZE_V];//可利用资源向量
int Allocation[MAXSIZE_P][MAXSIZE_V];//分配矩阵
int Request[MAXSIZE_P][MAXSIZE_V];//请求矩阵
int Work[MAXSIZE_V];//工作向量
int LP[MAXSIZE_P] = {0};//进程向量，初值置为0
int m, n;//资源的种类、进程的数目
vector<int> safeList; //安全序列 

//函数定义及说明
void initProcess();//初始化进程 【使用文件读取】
void SimplifyProcess();//简化进程
void PrintProcess();//打印当前进程信息
bool isLocked();//判断是否死锁
void saveProcess();//存入进程信息

int main(){
	//使用银行家算法化简
	cout << "=========进程死锁的检测==========" << endl;
	int choice;
	while(true){
		cout << "1、输入进程信息并将其存入文件\n";
		cout << "2、直接读取文本信息中的进程信息\n";
		cout << "请输入选择：";
		cin >> choice;
		if(choice == 1){
			//输入资源种类数
			cout << "请输入资源种类的数量：";
			cin >> m;
			//输入可用资源数
			cout << "请输入各种资源的数量当前可用的数量：\n";
			for(int i=0; i<m; i++){
				cout << "请输入资源【R" << (i+1) << "】当前可用的数量：";
				cin >> Available[i];//输入可用资源
			}
			//输入进程数目
			cout << "请输入进程的数量：";
			cin >> n;
			//进程当前对各类资源的请求数目
			cout<<"\n请输入进程当前对各类资源的请求数目：\n";
			for(int i=0; i<n; i++){
				cout<<"请输入进程【P" << (i+1) <<"】当前对各类资源的请求数目，用空格隔开):";
				for(int j=0; j<m; j++){
			    	cin >> Request[i][j];
				}
			}
			//读入进程已分配各种资源的数目
			cout<<"\n请输入进程已分配各种资源的数目：\n";
			for(int i=0; i<n; i++){
				cout<<"请输入进程【P" << (i+1) <<"】已分配各种资源的数量，用空格隔开):";
				for(int j=0; j<m; j++){
			 	   cin >> Allocation[i][j];
				}
			}
			saveProcess();//保存输入的信息
			break;//跳出循环开始简化
		}else if(choice == 2){
			//获取当前状态
			initProcess(); //直接读取文本信息里的进程信息
			break;//跳出循环开始简化
		}else{
			cout << "请输入正确的选项！\n";
		}
	}

	//尝试简化
	SimplifyProcess();//调用简化进程的函数
	//输出结果
	if(!isLocked()){//未死锁
		cout<<"\n该系统不会发生死锁！";
	}else{
		cout<<"\n该系统会发生死锁！以下是死锁的进程及资源！\n";
		cout << "进程名   已经分配   还需要的资源" << endl;
		for(int i=0; i<n; i++){
			if(LP[i] == 0){//LP为0的就是还需要进行资源分配的，也就是还未化简
				cout << "P" << (i+1) << "\t( ";
				for(int j=0; j<m; j++){
					cout << Allocation[i][j] << " ";//打印出此进程对于各类资源的已分配数量
				}
				cout << ")" << "\t( ";
				for(int j=0; j<m; j++){
					cout << Request[i][j] << " ";//打印出此进程对于各类资源还需要的数量 【使用请求的减去已分配的就是还需要的，Request-Allocation】
				}
				cout << ")" << endl;
			}
		}
	}
}

void initProcess(){//初始化进程 【使用文件读取】
	FILE *fp;
	fp = fopen("initProcess.txt", "r");
	if(fp == NULL){
		cout <<"文件打开失败，进程初始化失败！\n";
		return;
	}
	//先读入资源种类数
	fscanf(fp, "%d\n", &m);
	//读入可用资源数
	for(int i=0; i<m; i++){
		fscanf(fp, "%d ", &Available[i]);
	}
	fscanf(fp, "\n");//读入一个换行符

	//读入进程数目
	fscanf(fp, "%d\n", &n);

	//读入进程当前对各类资源的请求数目
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			fscanf(fp, "%d ", &Request[i][j]);
		}
		fscanf(fp, "\n");//读入一个换行符
	}
	//读入进程已分配各种资源的数目
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
	 	   fscanf(fp, "%d ", &Allocation[i][j]);
		}
		fscanf(fp, "\n");//读入一个换行符
	}
	fclose(fp);//关闭文件
	//输出读取到的数据
	cout << "资源的种类数：" << m << endl;//资源种类数，资源用R表示，如R1，R2等
	cout << "每个资源的数目：\n";
	for(int i=0; i<m; i++){//循环输出每个资源的数目
		cout << "资源【R" << (i+1) << "】的数量：" << Available[i] << endl;
	}
	cout << "进程数目：" << n <<endl;//进程数目，进程用P表示，如P1，P2
	cout << "每个进程所需各个资源的数量：" <<endl;
	for(int i=0; i<n; i++){//双层循环输出各个进程对各个资源的需求数
		cout <<"进程【P" << (i+1) << "】对于各个资源的需求数：" << endl;
		for(int j=0; j<m; j++){
			cout << Request[i][j] << " ";
		}
		cout << "\n\n";
	}
	cout << "每个进程已经分配到各个资源的数量：" <<endl;
	for(int i=0; i<n; i++){//双层循环输出各个进程已分配到的各个资源的数量
		cout <<"进程【P" << (i+1) << "】对于各个资源已经分配到的资源数：" << endl;
		for(int j=0; j<m; j++){
			cout << Allocation[i][j] << " ";
		}
		cout << "\n\n";
	}
}

void saveProcess(){//存入进程信息
	FILE *fp;
	fp = fopen("initProcess.txt", "w");//以写的方式打开文件
	if(fp == NULL){//文件打开失败
		cout <<"文件打开失败，进程初始化失败！\n";
		return;
	}
	//先写入资源种类数
	fprintf(fp, "%d\n", m);
	//写入可用资源数
	for(int i=0; i<m; i++){
		fprintf(fp, "%d ", Available[i]);
	}
	fprintf(fp, "\n");//写入一个换行符
	//写入进程数目
	fprintf(fp, "%d\n", n);
	//写入进程当前对各类资源的请求数目
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			fprintf(fp, "%d ", Request[i][j]);
		}
		fprintf(fp, "\n");//写入一个换行符
	}
	//写入进程已分配各种资源的数目
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
	 	   fprintf(fp, "%d ", Allocation[i][j]);
		}
		fprintf(fp, "\n");//写入一个换行符
	}
	fclose(fp);//关闭文件
}

void SimplifyProcess(){//简化进程
	//检测算法
	//银行家算法，起始工作资源等于可用资源
	for(int i=0; i<m; i++){
		Work[i] = Available[i];
	}
	PrintProcess();//打印当前进程信息
	cout << "接下来进行化简操作...\n";
	//不占用资源的进程计入LP中，也就是将当前已经完成资源分配的进程除去，并将其LP记为1，LP对应下标单元置1
	int count = 0;//记录表中置1的个数
	int cnt = 0;//记录化简次数
	for(int i=0; i<n; i++){//循环n个进程，一个个判断是否进程已完成
		bool flag = false; //初始设为false
		for(int j=0; j<m; j++){
			if(Allocation[i][j]!=0 || Request[i][j]!=0){//如果已分配的资源或请求资源不为0的话，不能化简，代表其还需要进行资源分配
				flag = true;//设为true
				break;
			}
		}
		if(!flag){//已分配的资源和请求资源都为0，代表此进程已经完成，可用化简掉，将其Lp记为1
			LP[i]=1;//设为1
            safeList.push_back(i+1);
			count++;//数量+1
			cnt++;//化简次数+1
			//化简后
			cout << "第【" << cnt << "】化简后...\n";
			PrintProcess();//打印当前进程信息
		}
	}

	//对所有未进入LP中的进程，尝试将其化简
	for(int k=0; k<n-count; k++){//还剩几个进程循环几轮
		for(int i=0; i<n; i++){//循环n个进程
			bool flag = false;//初始flag为false，以下经过资源分配后如果还是false说明分配成功
			if(LP[i] == 0){//LP为0的就是还需要进行资源分配的
				for(int j=0; j<m; j++){//测试是否Request<=Work
					if(Request[i][j] > Work[j]){//有一类资源不能满足进程的数量需求，那就不能分配
						flag = true;//设成true
						break;
					}
				}
				if(flag==0){//化简，收回所有边
					for(int j=0; j<m; j++){//循环各类资源，收回各类资源
						Work[j] += Allocation[i][j];//当前的工作资源【也可以说是可用资源】的数量 = 原本的加上化简掉的进程已分配的资源
			    	}
		 		    LP[i] = 1;//记入表中
                    safeList.push_back(i+1);
		 		    cnt++;//化简次数+1
					//化简后
					cout << "第【" << cnt << "】化简后...\n";
					PrintProcess();//打印当前进程信息
		 		}
		 	}
    	}
	}
}

void PrintProcess(){//打印当前进程信息
	int count = 0;//计算还有多少进程未完成，也就是未简化
	cout << "当前的可以资源剩余（ ";
	for(int i=0; i<m; i++){
		cout << Work[i] << " ";
	}
	cout << ")\n";
	cout <<"当前未化简的进程以及它已经分配的资源数，它所需的资源和对应的资源数如下：" <<endl;
	cout << "进程名   已经分配   还需要的资源" << endl;
	for(int i=0; i<n; i++){
		if(LP[i] == 0){//LP为0的就是还需要进行资源分配的，也就是还未化简
			count++;//未化简的进程数量+1
			cout << "P" << (i+1) << "\t( ";
			for(int j=0; j<m; j++){
				cout << Allocation[i][j] << " ";//打印出此进程对于各类资源的已分配数量
			}
			cout << ")" << "\t( ";
			for(int j=0; j<m; j++){
				cout << Request[i][j] << " ";//打印出此进程对于各类资源还需要的数量
			}
			cout << ")" << endl;
		}
	}
	if(count == 0){//数量为0代表进程已经全部被化简了
		cout << "进程已全部化简！" <<endl;
		cout << "存在安全序列：（";
		for(int s : safeList){
			cout << "P" << s << " "; 
		}
		cout << "）" << endl;
	}
	cout << endl;
}

bool isLocked(){//判断是否死锁
//判断是否所有进程都被回收
	for(int i=0; i<n; i++){
		if(LP[i] == 0){//有一个进程未完成，也就是未化简，就是死锁
			return true;
		}
	}
	return false;//循环之后还没有返回false，那就是全部LP都为1，也就是都化简了，返回false
}

